package com.xubaohua.八大排序;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @program: 冒泡排序 时间复杂度O(n^2)
 * @description:
 * @author: 许宝华
 * @create: 2022-04-14 12:45
 */

/**
 * 冒泡排序的基本思想是：通过对待排序序列从前向后（从下表较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，
 * 使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。数组共有n个元素，则需要比较n-1次。
 */
public class BubbleSort {

    public static int num =1;

    public static void main(String[] args) {
        int[] arr = new int[]{8,-1,19,-7,20};
        //模拟多数据排序
        int[] arrMax = new int[10000];
        for (int i = 0; i <10000 ; i++) {
            arrMax[i] = (int)(Math.random() * 8000000);
        }
//        int[] arr = new int[]{1,2,3,4,20};
//        bubbleSort1(arr);
//        bubbleSort2(arr);

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date);
        System.out.println(format);

        bubbleSort3(arrMax);

        Date date1 = new Date();
        String format1 = simpleDateFormat.format(date1);
        System.out.println(format1);
    }

    /**
     * 冒泡排序
     * @param arr
     */
    private static void bubbleSort1(int arr[]){
        int temp = 0;
        for (int i = 0; i < arr.length-1; i++) {
            //如果前面的数大于后面的，则发生交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第一趟排序后的数组--->" + Arrays.toString(arr));

        for (int i = 0; i < arr.length-1-1; i++) {
            //如果前面的数大于后面的，则发生交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;

            }

        }
        System.out.println("第二趟排序后的数组--->" + Arrays.toString(arr));

        for (int i = 0; i < arr.length-1-2; i++) {
            //如果前面的数大于后面的，则发生交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第三趟排序后的数组--->" + Arrays.toString(arr));

        for (int i = 0; i < arr.length-1-3; i++) {
            //如果前面的数大于后面的，则发生交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第四趟排序后的数组--->" + Arrays.toString(arr));
    }

    /**
     * 冒泡排序优化
     * @param arr
     */
    private static void bubbleSort2(int arr[]){
        int temp = 0;
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i ; j++) {
                if(arr[j] > arr[j+ 1]){
                    temp = arr[j];
                    arr[j] = arr[j+ 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"趟排序后的数组--->" + Arrays.toString(arr));
        }
    }
    /**
     * 冒泡排序优化，如果没有进行交换则直接退出，证明是有序的
     * @param arr
     */
    private static void bubbleSort3(int arr[]){

        int temp = 0;
        //标识符
        boolean flag = false;
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i ; j++) {
                if(arr[j] > arr[j+ 1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+ 1];
                    arr[j + 1] = temp;
                }
            }
//            System.out.println("第"+(i+1)+"趟排序后的数组--->" + Arrays.toString(arr));

            if(!flag){
                break;
            }else{
                flag = false;
            }
        }
    }
}
